package com.twogroup;


/**
 * @author binghan
 * @version 1.0
 * @description: TODO 自定义双向链表实现（我的双向链表头节点只有next，尾节点只有pre，不做循环）
 * @date 2022/5/11 19:16
 */
public class CustomLinkedList<E> {

    /**
     * 链表的每个Node节点
     */
    public class Node {
        private E data;
        private Node pre;
        private Node next;

        public Node() {
            // 构造函数默认赋值null
            this(null, null, null);
        }

        /**
         * 节点的数据构造方法
         *
         * @param data
         */
        public Node(E data) {
            this.data = data;
            this.pre = null;
            this.next = null;
        }

        /**
         * 带参构造函数
         *
         * @param data
         * @param pre
         * @param next
         */
        public Node(E data, Node pre, Node next) {
            this.data = data;
            this.pre = pre;
            this.next = next;
        }

        /**
         * 重写输出数据
         *
         * @return
         */
        @Override
        public String toString() {
            return data.toString();
        }
    }

    /**
     * 头节点
     */
    private Node head;

    /**
     * 尾节点
     */
    private Node tail;


    public CustomLinkedList() {
        head = null;
        tail = null;
    }

    /**
     * 头插法
     * 1. 为空链表的情况下怎么去做
     * 2.其他情况下的做法，这时我们不仅要关注next的值，还要关注prev的值 以及头节点的变化
     *
     * @param element
     * @return
     */
    public void addFirst(E element) {
        // 创建新节点
        Node node = new Node(element);
        // 处理是空链表时的情况 即头节点为空
        if (this.head == null) {
            // 设置头节点为新增节点,尾节点也为新增节点
            this.head = node;
            this.tail = node;
        } else {
            //正常情况，next和prev都要进行处理
            // 插入节点next原头节点
            node.next = this.head;
            // 原头节点pre插入节点
            this.head.pre = node;
            // 插入节点现作为头节点
            this.head = node;
        }
    }

    /**
     * 尾插法
     * 与头插法的思路大致相同，分为两部分：
     * 1. 空链表情况下
     * 2. 其他情况下，同样要关注 next 和 prev 的值
     *
     * @param element
     * @return
     */
    public void addLast(E element) {
        // 创建新节点
        Node node = new Node(element);
        // 处理是空链表时的情况 即头节点为空
        if (this.head == null) {
            // 设置头节点为新增节点,尾节点也为新增节点
            this.head = node;
            this.tail = node;
        } else {
            //正常情况，next和prev都要进行处理
            // 插入节点pre原尾节点
            node.pre = this.tail;
            // 原尾节点next插入节点
            this.tail.next = node;
            // 插入节点现作为尾节点
            this.tail = node;
        }
    }

    /**
     * 指定下标插入节点（主要）(从0下表开始到size-1为合法)
     * 代码的逻辑顺序应满足以下要求：
     * 1.先判是否为空链表
     * 2.然后判断index(下标)的值是否合法，合法范围：0<= index<= size()(链表当前的节点个数)
     * 3.先处理在 index == 0 的情况下插入数据，直接使用头插法（addFirst）
     * 4.再处理在 index == size（）的情况下插入数据，使用尾插法（addLast）
     * 5.最后处理正常情况（在双链表中只要找到了index指向的那个节点就可以直接插入新节点）
     *
     * @param index
     * @param element
     * @return 插入成功 true 失败 false
     */
    public boolean addIndex(int index, E element) {
        // 判断是否是空链表
        if (this.head == null) {
            return false;
        }
        // 判断坐标是否合法
        if (index > size() || index < 0) {
            System.out.println("下标不合法!");
            return false;
        }
        // 在0位置插入
        if (index == 0) {
            // 头插法
            addFirst(element);
            return true;
        }
        // 在末尾插入
        if (index == size()) {
            // 尾插法
            addLast(element);
            return true;
        }
        // 创建节点
        Node node = new Node(element);
        // 循环遍历找到index指向的节点
        Node cur = this.head;
        while (index > 0) {
            cur = cur.next;
            index--;
        }
        // 此时cur为index指向的节点（思考 插入节点占用该节点位置，该节点要右移动，所以左插）
        // 插入新节点
        // 插入节点next原位置节点
        node.next = cur;
        // 插入节点pre原位置节点pre
        node.pre = cur.pre;
        // 原位置节点pre next插入节点
        cur.pre.next = node;
        // 原位置节点pre插入节点
        cur.pre = node;
        return true;
    }

    /**
     * 查找指定元素data是否在单链表当中
     * 这个方法比较简单，就是循环遍历链表就可以了。只需要注意遍历时不要直接使用head
     *
     * @param data
     * @return
     */
    public boolean contains(E data) {
        // cur作为head来直接遍历
        Node cur = this.head;
        while (cur != null) {
            if (cur.data == data) {
                return true;
            }
            //往后走
            cur = cur.next;
        }
        return false;
    }

    /**
     * 删除所有值为data的节点
     *
     * @param data
     */
    public void removeAll(E data) {
        //判断是否为空链表
        if (this.head == null) {
            return;
        }
        //先处理正常情况
        Node cur = this.head.next;
        //循环遍历链表
        while (cur != null) {
            //找到了
            if (cur.data == data) {
                //先判断是不是尾节点
                if (cur.next == null) {
                    //是尾节点，进行处理
                    cur.pre.next = null;
                    cur.pre = null;
                } else {
                    //不是尾结点，就这样处理
                    cur.pre.next = cur.next;
                    cur.next.pre = cur.pre;
                }
            }
            cur = cur.next;   //该节点是与不是都要往后走
        }
        //处理头节点的情况
        if (this.head.data == data) {
            this.head = this.head.next;
            //判断头节点处理完毕后是不是成了一个空链表
            if (this.head != null) {
                this.head.pre = null;
            }
        }
    }

    /**
     * 打印双链表
     */
    public void display() {
        // cur作为head节点来遍历
        Node cur = this.head;
        while (cur != null) {
            System.out.print(cur.data + " ");
            cur = cur.next;
        }
        //换一下行
        System.out.println();
    }


    /**
     * 得到双向链表的长度
     *
     * @return
     */
    public int size() {
        int count = 0;
        // 获取头节点
        Node cur = this.head;
        // 节点不为空
        while (cur != null) {
            // 数量加一 当前节点cur为下一个节点
            count++;
            cur = cur.next;
        }
        return count;
    }


}
